package com.kaizen.leet448;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 官方题解
 *
 *
 * 作者：LeetCode
 * 链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/zhao-dao-suo-you-shu-zu-zhong-xiao-shi-de-shu-zi-2/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 *
 * @author kaizen
 * @date 2020/5/16 12:23
 */
class Solution {

    /**
     * 方法一：使用哈希表
     * 我们假设数组大小为 N，它应该包含从 1 到 N 的数字。但是有些数字丢失了，我们要做的是记录我们在数组中遇到的数字。然后从 1\cdots N1⋯N 检查哈希表中没有出现的数字。我们用一个简单的例子来帮助理解。
     *
     * 算法：
     *
     * 我们用一个哈希表 hash 来记录我们在数组中遇到的数字。我们也可以用集合 set 来记录，因为我们并不关心数字出现的次数。
     * 然后遍历给定数组的元素，插入到哈希表中，即使哈希表中已经存在某元素，再次插入了也会覆盖
     * 现在我们知道了数组中存在那些数字，只需从 1\cdots N1⋯N 范围中找到缺失的数字。
     * 从 1\cdots N1⋯N 检查哈希表中是否存在，若不存在则添加到存放答案的数组中
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers1(int[] nums) {

        // Hash table for keeping track of the numbers in the array
        // Note that we can also use a set here since we are not
        // really concerned with the frequency of numbers.
        HashMap<Integer, Boolean> hashTable = new HashMap<Integer, Boolean>();

        // Add each of the numbers to the hash table
        for (int i = 0; i < nums.length; i++) {
            hashTable.put(nums[i], true);
        }

        // Response array that would contain the missing numbers
        List<Integer> result = new LinkedList<Integer>();

        // Iterate over the numbers from 1 to N and add all those
        // that don't appear in the hash table.
        for (int i = 1; i <= nums.length; i++) {
            if (!hashTable.containsKey(i)) {
                result.add(i);
            }
        }

        return result;
    }

    /**
     * 最优解
     * 【笔记】将所有正数作为数组下标，置对应数组值为负值。那么，仍为正数的位置即为（未出现过）消失的数字。
     * 我们需要知道数组中存在的数字，由于数组的元素取值范围是 [1, N]，所以我们可以不使用额外的空间去解决它。
     * 我们可以在输入数组本身以某种方式标记已访问过的数字，然后再找到缺失的数字。
     * 算法：
     *
     * 遍历输入数组的每个元素一次。
     * 我们将把 |nums[i]|-1 索引位置的元素标记为负数。
     * 即 nums[|nums[i] |- 1] \times -1nums[∣nums[i]∣−1]×−1 。
     * 然后遍历数组，若当前数组元素 nums[i] 为负数，说明我们在数组中存在数字 i+1
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/zhao-dao-suo-you-shu-zu-zhong-xiao-shi-de-shu-zi-2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers2(int[] nums) {

        // Iterate over each of the elements in the original array
        for (int i = 0; i < nums.length; i++) {

            // Treat the value as the new index
            int newIndex = Math.abs(nums[i]) - 1;

            // Check the magnitude of value at this new index
            // If the magnitude is positive, make it negative
            // thus indicating that the number nums[i] has
            // appeared or has been visited.
            if (nums[newIndex] > 0) {
                nums[newIndex] *= -1;
            }
        }

        // Response array that would contain the missing numbers
        List<Integer> result = new LinkedList<Integer>();

        // Iterate over the numbers from 1 to N and add all those
        // that have positive magnitude in the array
        for (int i = 1; i <= nums.length; i++) {

            if (nums[i - 1] > 0) {
                result.add(i);
            }
        }

        return result;
    }

}
